package binarytree;

import Node.TreeNode;

public class DecomposeMaxDepth {

    /**
     * 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
     * @param root
     * @return
     */
    public int decomposeMaxDepth(TreeNode root) {
        if (root == null)
            return 0;
        // 利用定义，计算左右子树的最大深度
        int leftMax = decomposeMaxDepth(root.left);
        int rightMax = decomposeMaxDepth(root.right);
        // 后序遍历位置
        // 根据左右子树的最大深度推测出原二叉树的最大深度
        // 整棵树的最大深度等于左右子树的最大深度取最大值
        // 然后加上根节点自己
        return 1 + Math.max(leftMax, rightMax);
    }
}
